1. Field of the Invention
The present invention generally relates to pattern recognition systems, and particularly to the detection of a circle from a complex image that combines circles, straight lines, and other shapes.
2. Related Art
The science of digital image processing involves the transformation of an image into digital data to be processed by a digital computer. Digital image analysis concerns the description and interpretation of that digital data in order to recognize the content of the image that was transformed.
Digital image processing and consequently digital image analysis first begin with the process of forming the digital image. Typically, a system or device for forming digital images includes an optical system, a sensor, and a digitizer. The optical system typically scans an object or image to create optical signals. The sensor in turn detects those optical signals and converts them into analog electrical signals. The digitizer then converts those analog electrical signals into digital signals that represent the original object or image.
Digital image analysis generally begins with determining the boundaries of an object by detecting the edges and lines which define the image of the object. Once the boundaries are detected, coordinates for those boundaries are generated. The present invention primarily concerns the process for determining object boundaries based the detection of edges.
In Digital Image Processing Algorithms by Ioannis Pitas, Prentice Hall International (UK) Ltd., Prentice Hall Incorporated, Englewood Cliffs, N.J. 1993, p. 223, which is incorporated by reference herein, an image edge is generally defined as the border between two homogeneous image regions having different illumination intensities. In other words, an image edge is defined by local variations of illumination or intensity. Therefore, image edges may be detected by applying known methods for determining local illumination or intensity differences. One such technique uses a Sobel operator or Sobel edge detector mask, which will be applied in the present invention. For the purposes of the invention, edge pixels are defined as the pixels along the border between two image regions of different intensities. The difference between the intensity of pixels in one region on one side of the edge pixels and the intensity of pixels in the other region on the other side of the edge pixels is a relative maximum.
Local image intensity variations can be described in terms of image gradients such as: EQU .gradient.M(x,y)=[.delta.M/.delta.x .delta.M/.delta.y].sup.T .DELTA.[M.sub.x M.sub.y ].sup.T
where .gradient.M(x,y) represents the image gradient for an individual pixel. A gradient vector may then be calculated for the individual pixel in terms of its magnitude M(x,y) and direction D(x,y) where ##EQU1##
The Sobel operator or edge detection mask is a matrix pattern of values (See FIG. 5B) that is applied to a matrix representing the intensity values of a selected image pixel and the neighborhood of pixels surrounding the selected pixel. When the Sobel operator is applied, a gradient vector for that selected pixel may be calculated.
In digital image analysis, the conventional approach for detecting a circle in a complex image is the Hough Transformation. The Hough Transformation is a method for detecting straight lines and curves on grey level images, as defined in Computer and Robot Vision--Volume I, Addison-Wesley Publishing Company, Reading, Mass. 1992, pp. 578-585 by Haralick et al. This book by Haralick et al. is hereby incorporated by reference.
Even though the Hough Transformation is widely used, there are problems in its application. One such problem is in determining the threshold levels for assigning values to the accumulator array used by the transformation. For example, if the threshold levels for inputting values into the accumulator array are too low, the transformation generates too many values some of which may be erroneous. If the threshold levels are too high, the transformation cannot generate enough values to detect a circle.
The detection and recognition of a circle is particularly significant in the imaging analysis of objects containing identifying marks based on a circle. For example, confidential documents are often marked or stamped to indicate their status. That confidential status in many cases requires that the documents not be copied without proper authorization. However, current methods for preventing unauthorized copying of documents only include having the documents made with colors and/or materials that cannot be copied, denying anyone handling the documents access to a copier, or denying access to the documents completely. Such methods clearly are inefficient and can be expensive.
One possible application of the invention is the detection of the mark or stamp on a document that indicates its confidential status. In this case, the mark or stamp includes a circular border, such as that shown in FIG. 3, Image 0. An image processing apparatus (e.g., a photocopier, a facsimile machine) can be designed to detect such a mark on a document it is handling, and to stop the copying or transmission of the document, or to warn of the unauthorized copying or transmission if it detects such a mark.
In this application, the invention has the advantage of not requiring any special materials that may be awkward or costly to use. Rather, conventional paper or its equivalent can be used as long as the documents are marked properly. Also, the invention eliminates the need for any special handling procedures that are inefficient or time-consuming. Image processing apparatus equipped with the invention would simply prevent unauthorized copying or transmission of the documents.